A navigation system performs travel guidance for enabling a user to easily and quickly reach the selected destination. A typical example is a vehicle navigation system which guides a driver of a vehicle to a destination through a calculated route. Such a navigation system detects the position of the user's vehicle, and reads out map data pertaining to an area at the current vehicle position from a data storage medium, for example, a CD-ROM (compact disc read-only memory), a DVD (digital versatile disc), or a hard disc. Typically, the navigation system displays a map image on a monitor screen while superimposing thereon a mark representing the current location of the user' vehicle. At an intersection on the calculated route, the navigation system notifies the user which direction to turn.
FIG. 1 is a schematic diagram showing an example as to how the conventional map data is constructed into mesh structured data for application to a navigation system. In this example of map data, a map area 23 is a graphical representation of a selected area such as a county, a city, etc., that is generated by the original map data provided by a map data provider. Typically, such original map data is in a GDF (Geographic Data File) format which is an interchange file format structure by plain text file. In the mesh structured data of FIG. 1, the map area 23 is divided into a plurality of meshed portions (map cells) 21a-21i each typically having a rectangular shape of a predetermined size.
When a destination is set, a navigation system retrieves and processes the map data to produce a calculated route, which is an appropriate route to the destination determined by predefined methods. During a route guidance operation to the destination, the navigation system successively retrieves the map data associated with the calculated route from the data storage medium and stores such map data in a map memory and reads the map data in the map memory for conducting the route guidance operation. The map data for the navigation system must include a vast amount of information such as road shapes, absolute locations, road classes, allowable speeds and other traffic regulations, POI (point of interest) information, POI icons, map icons, etc. Thus, the process of storing and retrieving such a large amount of map data during the route guidance operation can be time consuming and inefficient.
In order to resolve such burdens, the map data used for a navigation system is typically structured in a multiple layer data format. FIG. 2 is a schematic diagram showing an example of such a multiple layer data format of the map data used in the navigation system. As shown, the format of the map data in FIG. 2 is configured by a plurality of layers 11A-11D each representing a part of the map data to be stored in a map data storage or a map database of the navigation system.
Further, as noted above, the map data in each of the layers 11A-11D is divided into a plurality of meshes or map cells represented by reference numerals 13. Namely, the map data is hierarchically layered corresponding to the level of details of the map information as well as divided corresponding to the size or amount of the map data. In the example of FIG. 2, the higher the layer of the hierarchy, the lower the detailedness of the map information and the larger the mesh size which is equivalent to the covering area.
Typically, the higher layer represents only high class roads, for example, interstate highway, freeway, etc. while the lower layer represents low class roads, i.e., residential roads, etc., POI icons, building foot prints, etc., in addition to that represented by the higher layers. One of the reasons for using the layered structure is to accommodate several different map scales for enlarging or shrinking the map image on the display screen on the navigation system. Since the lower layer includes more detailed map information, the size of the mesh 13 (covering area) is smaller than that of the higher layer to maintain the amount of map data within a predetermined range.
In FIG. 2, although the same numerals 15 are used to indicate various roads on the layers, the classes of the roads represented by them are not the same. Namely, the roads 15 in the higher layers represent only the high class roads while the roads 15 in the lower layer includes all the classes of roads of the upper layers and the current layer. Further, as noted above, the map data in each data layer is divided into a plurality of meshes or map cells 13 each having a rectangular shape of a predetermined size.
Since the map data is treated as a unit of mesh (map cell) 13 as shown in FIG. 2, the navigation system does not have to process an excessively large amount of map data at a time. Namely, the navigation system processes the map data corresponding to each unit of the mesh. The layer 11A shown in FIG. 2 is comprised of one mesh 13A while the layer 11B is comprised of four meshes 13B, and the layer 11C is comprised of eight meshes 13C while the layer 11D is comprised of sixteen meshes 13D. Thus, the performance limitation that may be caused by the hardware power of the navigation system can be alleviated by maintaining the map data within the suitable size.
The data format based on the meshed layers described above has disadvantage in that generating and modifying the map data is complex and time-consuming. Moreover, the data format is not logically related to an actual geographic area, i.e., the meshes are not logically related to the actual shape of city or state boundaries. Therefore, it is desired that map data be organized in a more logical and intuitive manner while allowing easy modification, and a search method for such map data be conducted so as to take advantage of the city/state boundary for efficient route searching.